package com.captain.leetcode2.链表;

import com.captain.leetcode.链表.ListNode;

/**
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
 * 如果是，返回 true ；否则，返回 false 。
 * <p>
 * 输入：head = [1,2,2,1]
 * 输出：true
 */
public class 回文链表234 {

    public static void main(String[] args) {
        new 回文链表234().isPalindrome(ListNode.getInstance());

    }

    public boolean isPalindrome(ListNode head) {
        if (head == null) return false;
        if (head.next == null) return true;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode back = slow.next;
        slow.next = null;
        //反转back
        back = revere(back);
        //两个链表的值是否相同
        ListNode pre = dummy.next;
        while (pre != null && back != null) {
            int preValue = pre.val;
            int backValue = back.val;
            if (preValue != backValue) return false;
            pre = pre.next;
            back = back.next;
        }
        if (pre == null && back == null) return true;
        if (pre.next == null) return true;
        return false;
    }

    public ListNode revere(ListNode head) {
        if (head == null) return head;
        // 1 2 3 4
        ListNode pre = null;
        while (head != null) {
            ListNode tp = head.next;
            head.next = pre;
            pre = head;
            head = tp;
        }
        return pre;
    }
}
